The FEC (Forward Error Correction) is known as a method for recovering an original packet in case of occurrence of packet loss in a transmission line. In the FEC method, in a transmission line with a packet loss possibility, a sending terminal sends a source packet with an encoded packet added to it, to a network. When there is a packet not received by a reception terminal, the reception terminal recovers the lost packet on the basis of a corresponding encoded packet.
There is one class of the FEC method called “rateless codes” (also called “fountain codes”) in which redundant packets are generated limitlessly from source packets, and the source packets are decoded from the redundant packets at a reception terminal.
There is known a method, included in the rateless codes, which, when an unidentified source packet exists at a time of decoding, calculates a matrix generated from encoded packets on the basis of Gaussian elimination, thereby decoding the source packet from the encoded packets (Non-patent Literature 1 (NPL 1), Patent Literature 1 (PTL 1)).
FIG. 8 is a block diagram showing an example of a configuration of a communication system (encoded packet transmission/reception system) comprising terminals according to the related art. Referring to FIG. 8, a sending terminal 10 and a reception terminal 20 are connected with each other via a network 30. The sending terminal 10 comprises a source packet sending unit 12, a packet encoding unit 14 and a packet sending unit 16. On the other hand, the reception terminal 20 comprises a packet reception unit 22, a packet decoding unit 24 and a source packet reception unit 26.
FIG. 9 is a block diagram showing an example of a configuration of the packet decoding unit 24 in the reception terminal 20 of FIG. 8. Referring to FIG. 9, the packet decoding unit 24 comprises a packet decoding calculation section 28 and a decoding determination section 36. Further, the packet decoding calculation section 28 comprises a Gaussian elimination part 32 and stores a decoding matrix 34.
The communication system according to the related art having the above-described configuration operates as follows. FIG. 10 shows an example of a state where the packet coding unit 14 of the sending terminal 10 encodes packets and a state where the packet decoding section 24 of the reception terminal 20 decodes the encoded packets.
First, operation of the sending terminal 10 will be described. The source packet sending unit 12 sends generated N number of source packets 38 to the packet coding unit 14. The packet coding unit 14 selects packets at random from among the received N number of source packets 38, and generates a packet obtained by exclusive OR (XOR) operation on the selected packets as one of encoded packets 42. The packet coding unit 14 adds arrays each indicating source packets used in generating the corresponding one of the encoded packets 42 (a random matrix G illustrated in FIG. 10), to the encoded packets 42. Further, the packet coding unit 14 sends thus generated encoded packets 42 to the packet sending unit 16. The packet sending unit 16 sends the encoded packets 42 it thus received to the network 30. Accordingly, in FIG. 10, packets consisting of respective rows of the random matrix G and respective rows of the encoded packets 42 are sent by the packet sending unit 16. Specifically, in the example shown in FIG. 10, the random matrix G is that of six rows by five columns. There, based on the five source packets 38 (N=5), for example, a 6-bit packet denoted as [0, 1, 1, 1, 1, p2{circumflex over ( )}p3{circumflex over ( )}p4{circumflex over ( )} p5 (denoting a result of XOR operation on p2, p3, p4 and p5, which is, for example, 1)] which is obtained by adding the first row of the random matrix G to the first row of the encoded packets 42. Similarly, for example, packets consisting of respective ones of the second to sixth rows of the random matrix G and those of the encoded packets 42 are sent. Accordingly, the source packets 38 are sent in the form of six 6-bit packets.
Next, operation of the reception terminal 20 will be described. The packet reception unit 22 sends encoded packets 44 it received via the network 30 to the packet decoding unit 24. The packet decoding unit 24 performs decoding operation each time receiving a packet, thereby trying to decode the encoded packets 44 into N number of source packets 46. As shown in FIG. 10, the packet decoding unit 24 uses, for example, a general decoding method which constructs arrays representing source packets and uses Gaussian elimination. When having succeeded in decoding the received encoded packets 44 into the N number of source packets 46, the packet decoding unit 24 sends the N number of source packets 46 to the source packet reception unit 26. In the example shown in FIG. 10, packet loss occurs to the fourth one of the six packets sent by the packet sending unit 16, and accordingly, five packets are received by the packet reception unit 22, where the number of received packets, 5, is a number not less than the number of the source packets 38. Therefore, from the received five packets, five simultaneous linear equations can be generated, where the number of linear equations, 5, is a number not less than the number of the source packets 38. Accordingly, based on the five simultaneous linear equations, the five source packets 38 can be derived by Gaussian elimination.
Here, a description will be given of Gaussian elimination, which is a general decoding method. FIG. 11 is a flow diagram showing an algorithm of decoding (Gaussian elimination) in the reception terminal 20 of the related art. Here, to simplify the present description, in FIG. 12, a matrix calculation process (i=1) is shown with respect to a case where the number of source packets, N, is 5, as an example of operation in each phase.
With reference to FIGS. 11 and 12, descriptions will be given of a general Gaussian elimination algorithm and of the matrix calculation process (i=1) with respect to a case where the number of source packets, N, is 5, as an example of description of the algorithm.
First, in a step A2, a row vector with its i-th element being 1 is selected from among the row vectors below the i-th row. At that time, if no such row vector to select is found (NO at a step A3), the calculation of Gaussian elimination is ended. In the case of the example of operation in FIG. 12, in a decoding matrix 34-1, a row vector with its first element being 1 among the row vectors below the i-th row is the fifth one, and accordingly, the fifth row vector is selected.
Then, in a step A4, the selected row vector is exchanged with the row vector of the first row. The i-th element of a row vector of the i-th row after the exchange is referred to as a “pivot”, and the row vector itself as a “pivot row”. In the case of the example of operation in FIG. 12 (i=1), the Gaussian elimination part 32 exchanges the row vector of the fifth row with that of the first row, in the decoding matrix 34-1. A decoding matrix 34-2 is the decoding matrix in the state after thus exchanging the row vectors.
Next, in a step A5, the Gaussian elimination part 32 performs XOR operation between the pivot row and a row vector with its i-th element being 1 other than the pivot row. In the case of the example of operation in FIG. 12 (i=1), there is no other row vector with its first element being 1 than the pivot row, in the decoding matrix 34-2, and accordingly, the Gaussian elimination part 32 performs no such XOR operation.
The Gaussian elimination part 32 performs the above-described operation for i=2 to 5 repeatedly, as described in steps A1 and A7. As shown in FIG. 12, when the calculation has been performed with respect to the rows down to the fifth row, a decoding matrix 34-X resulting from the application of Gaussian elimination becomes an identity matrix, where the encoded packets have been decoded.
Further, it may occur that, when the above-described operation has been completed for i=5, the sending terminal 10 sends the next group of source packets after encoding them. In that case, the steps for i=1 to 5 are repeated again several times.
In the case of the communication system according to the related art, the decoding by Gaussian elimination is performed each time receiving a packet. However, when the decoding method is used, it is possible that there occurs variance in the calculation amount among packet receptions or that the calculation amount after receiving the N-th encoded packet becomes large, and consequently that the calculation cannot be completed before the arrival of encoded packets with respect to the next source packets or some other problem occurs.
For example, in the case of the decoding matrix 34-1 in FIG. 12, the Gaussian elimination part 32 cannot apply Gaussian elimination in the step A3 until the encoded packet corresponding to the fifth row vector arrives, and accordingly cannot advance the calculation. That is, the calculation by the Gaussian elimination part 32 is started only after the arrival of the packet corresponding to the fifth row vector, which causes the Gaussian elimination part 32 to perform each of the process of the step A4 and that of the step A5 five times after the arrival of the packet corresponding to the fifth row vector.
As a result, at a time of their arrival, encoded packets with respect to the next group of source packets are required to wait until the calculation on the encoded packets with respect to the present group of source packets is completed.
As a method for increasing the speed of such calculation by Gaussian elimination in a communication system in which encoded packets are sent and received in the above-described manner, there is a method described in PTL 1, for example.